class Solution {
public:
    int rob(vector<int>& nums) {
        //
        int n=nums.size();
        vector<int> f(n);   //f[i] 偷
        vector<int> g(n);   //g[i] 不偷

        //初始化
        f[0]=nums[0],g[0]=0;
        //填表
        for(int i=1;i<n;i++)
        {
            f[i]=nums[i]+g[i-1];        //i处偷的+i-1处不偷的
            g[i]=max(g[i-1],f[i-1]);    //i-1处不偷的+i-1处偷的
        }
        //返回n-1处偷或者n-1处不偷的max
        return max(f[n-1],g[n-1]);
    }
};